为了增强局部搜索算法在求解最大割问题上的寻优能力，提高解质量，提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想，综合利用了“构造”和“扰动”这两种方法生成新的起始解，来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较，MSTS算法在18个算例上得到最好解值，高于其他对比算法。实验结果表明，MSTS算法具有更强的寻优能力和更高的解质量。
